package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/all-elements-in-two-binary-search-trees/'>两棵二叉搜索树中的所有元素(All Elements in Two Binary Search Trees)</a>
 * <p>给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root1 = [2,1,4], root2 = [1,0,3]
 *                  2           1
 *                 / \         / \
 *                1   4       0   3
 *      输出：[0,1,1,2,3,4]
 *
 * 示例 2：
 *      输入：root1 = [1,null,8], root2 = [8,1]
 *                  1          8
 *                   \        /
 *                    8      1
 *      输出：[1,1,8,8]
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>每棵树的节点数在 [0, 5000] 范围内</li>
 *     <li>-10^5 <= Node.val <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/23 15:13
 */
public class LC1305AllElementsInTwoBinarySearchTrees_M {

    static class Solution {
        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            dfs(root1, list1);
            dfs(root2, list2);
            int list1Size = list1.size();
            int list2Size = list2.size();
            // 合并两个有序数组
            List<Integer> allNodeValList = new ArrayList<>(list1Size + list2Size);
            int list1Index = 0, list2Index = 0;
            while (list1Index < list1Size && list2Index < list2Size) {
                if (list1.get(list1Index) < list2.get(list2Index)) {
                    allNodeValList.add(list1.get(list1Index++));
                } else if (list1.get(list1Index) > list2.get(list2Index)) {
                    allNodeValList.add(list2.get(list2Index++));
                } else {
                    allNodeValList.add(list1.get(list1Index++));
                    allNodeValList.add(list2.get(list2Index++));
                }
            }
            while (list1Index != list1Size) {
                allNodeValList.add(list1.get(list1Index++));
            }
            while (list2Index != list2Size) {
                allNodeValList.add(list2.get(list2Index++));
            }
            return allNodeValList;
        }

        private void dfs(TreeNode currNode, List<Integer> allNodeValList) {
            if (currNode == null) {
                return;
            }
            dfs(currNode.left, allNodeValList);
            allNodeValList.add(currNode.val);
            dfs(currNode.right, allNodeValList);
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(2);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(4);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(0);
        root2.right = new TreeNode(3);

        Solution solution = new Solution();
        Printer.printListInteger(solution.getAllElements(root1, root2));
    }
}
